Матч 187, Точка в многоугольнике (PointInPolygon)

Дивизион 2, Уровень 3

 

Для точки с координатами (testPointX, testPointY) определить, находится ли она вне, внутри или на границе простого многоугольника, координаты которого заданы в массиве строк vertices. В зависимости от результата вернуть одно из значений: “INTERIOR”, “EXTERIOR” или “BOUNDARY”.

Сторонами многоугольника являются вертикальные и горизонтальные отрезки, вершины имеют целочисленные координаты. Многоугольник является простым, если он не имеет самопересечений.

 

Класс: PointInPolygon

Метод: string testPoint(vector<string> vertices,

                        int testPointX, int testPointY)

Ограничения: массив vertices содержит от 4 до 50 строк вида “<x> <y>” (координаты вершин многоугольника), где x и y являются знаковыми числами и содержат от 1 до 4 цифр, -1000 £ <x>, <y> £ 1000, никакие три полседовательные вершины многоугольника не лежат на одной прямой, никакие две вершины не совпадают, ребра многоугольника не пересекаются, -1000 £ testPointX, testPointY £ 1000.

 

Вход. Координаты вершин многоугольника, заданные в массиве vertices, координаты тестовой точки testPointX и testPointY.

 

Выход. Одно из слов “INTERIOR”, “EXTERIOR” или “BOUNDARY” в зависимости от относительного положения точки (testPointX, testPointY) и многоугольника.

 

Пример входа

vertices

testPointX

testPointY

{"0 0", "0 10", "10 10", "10 0"}

5

5

{"0 0","0 10","10 10","10 0"}

5

10

{"0 0","0 10","10 10","10 0"}

10

15

 

Пример выхода

“INTERIOR”

“BOUNDARY”

“EXTERIOR"

 

 

РЕШЕНИЕ

геометрия

 

Функция OnSegment возвращает 1, если точка (x, y) лежит на вертикальном или горизонтальном сегменте (x1, y1) – (x2, y2). Для этого необходимо выполнение двух условий:

min(x1, x2) £ x £ max (x1, x2), min(y1, y2) £ y £ max (y1, y2)

Координаты len = vertices.size() вершин многоугольника считываем в массивы x[51], y[51], причем координаты последней занесенной точки полагаем равной нулевой (x[len] = x[0], y[len] = y[0]). Сначала проверяем, лежит ли тестируемая точка (testPointX, testPointY) на одной из сторон многоугольника. Если да – то возвращаем “BOUNDARY”.

Проведем луч из тестируемой точки в любом направлении. Если луч пересекает четное количество сторон, то точка лежит все многоугольника. Если количество пересечений луча и сторон будет нечетным, то точка находится внутри многоугольника. В качестве направления луча выберем такое, которое совпадает с направлением оси абсцисс. При этом некоторые стороны многоугольника могут касаться луча, создавая при этом неудобства при вычислениях. Для избежания этих неудобств подвинем тестируемую точку на вектор (½, ½), после чего умножим все координаты вершин многоугольника и тестируемой точки на 2. После такого преобразования положение точки относительно многоугольника не изменится, так как все исходные координаты являлись целочисленными, и горизонтальный луч не будет касаться ни одной из сторон многоугольника. При этом он будет пересекать только вертикальные отрезки. Горизонтальный луч, пущенный из точки (testPointX, testPointY) вправо, будет пересекать вертикальный отрезок (x1, y1) – (x2, y2) тогда и только тогда, когда:

testPointX < x1, x1 = x2, min(y1, y2) £ testPointY £ max (y1, y2)

В переменной с подсчитываем количество пересечений луча с вертикальными отрезками. Если это количество будет четным, то выводим “EXTERIOR”, иначе выводим “INTERIOR”.

 

 

ПРОГРАММА

 

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

 

class PointInPolygon

{

public:

 

  int OnSegment(int x1, int y1, int x2, int y2, int x, int y)

  {

    if ((min(x1,x2) <= x) && (x <= max(x1,x2)) &&

        (min(y1,y2) <= y) && (y <= max(y1,y2))) return 1;

    return 0;

  }

 

  string testPoint(vector<string> vertices, int testPointX, int testPointY)

  {

    int x[51] ,y[51], i, c, len;

    for(i = 0; i < (len = vertices.size()); i++)

      sscanf(vertices[i].c_str(),"%d %d",&x[i],&y[i]);

    x[len] = x[0]; y[len] = y[0];

    for(i = 0; i < len; i++)

      if (OnSegment(x[i],y[i],x[i+1],y[i+1],testPointX,testPointY))

        return "BOUNDARY";

    for(i = 0; i <= len; i++) {x[i] *= 2; y[i] *= 2;};

    testPointX = 2 * testPointX + 1;testPointY = 2 * testPointY + 1;

    for(c = i = 0; i < len; i++)

      if ((testPointX < x[i]) && (x[i] == x[i+1]) &&

          (min(y[i],y[i+1]) < testPointY) &&

          (testPointY < max(y[i],y[i+1]))) c++;

    if (c % 2) return "INTERIOR";

    return "EXTERIOR";

  }

};